翻訳と辞書 Words near each other ・ Karpowicze ・ Karpowo ・ Karpoš Municipality ・ Karppillikkavu Sree Mahadeva Temple ・ Karppinen ・ Karppooradeepam ・ Karptjärn ・ Karpuiyeh ・ Karpuragauram Karunavtaaram ・ Karpurkati ・ Karpuzlu ・ Karpuzlu, Kozluk ・ Karpylivka ・ Karpówek ・ Karp–Flatt metric ・ Karp–Lipton theorem ・ Karq Rig ・ Karqayin ・ KARR ・ KARR (AM) ・ KARR (Knight Rider) ・ Karr Tuttle Campbell ・ Karr-Koussevitzky ・ Karra Block ・ Karra Elejalde ・ Karra Subba Reddy ・ Karrab ・ Karrab Rural District ・ Karrab, Razavi Khorasan ・ Karrabin railway station Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Karp–Lipton theorem ： ウィキペディア英語版 Karp–Lipton theorem In complexity theory, the Karp–Lipton theorem states that if the boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then :$\backslash Pi\_2\; =\; \backslash Sigma\_2\; \backslash ,$ and therefore $\backslash mathrm\; =\; \backslash Sigma\_2.\; \backslash ,$ That is, if we assume that NP, the class of nondeterministic polynomial time problems, can be contained in the non-uniform polynomial time complexity class P/poly, then this assumption implies the collapse of the polynomial hierarchy at its second level. Such a collapse is believed unlikely, so the theorem is generally viewed by complexity theorists as evidence for the nonexistence of polynomial size circuits for SAT or for other NP-complete problems. A proof that such circuits do not exist would imply that P ≠ NP. As P/poly contains all problems solvable in randomized polynomial time (Adleman's theorem), the Karp–Lipton theorem is also evidence that the use of randomization does not lead to polynomial time algorithms for NP-complete problems. The Karp–Lipton theorem is named after Richard M. Karp and Richard J. Lipton, who first proved it in 1980. (Their original proof collapsed PH to $\backslash Sigma\_3$, but Michael Sipser improved it to $\backslash Sigma\_2$.) Variants of the theorem state that, under the same assumption, MA = AM, and PH collapses to complexity class. There are stronger conclusions possible if PSPACE, or some other complexity classes are assumed to have polynomial-sized circuits; see P/poly. If NP is assumed to be a subset of BPP (which is a subset of P/poly), then the polynomial hierarchy collapses to BPP.〔S. Zachos, Probabilistic quantifiers and games, 1988〕 If coNP is assumed to be subset of NP/poly, then the polynomial hierarchy collapses to its third level. == Intuition == Suppose that polynomial sized circuits for SAT not only exist, but also that they could be constructed by a polynomial time algorithm. Then this supposition implies that SAT itself could be solved by a polynomial time algorithm that constructs the circuit and then applies it. That is, efficiently constructible circuits for SAT would lead to a stronger collapse, P = NP. The assumption of the Karp–Lipton theorem, that these circuits exist, is weaker. But it is still possible for an algorithm in the complexity class $\backslash Sigma\_2$ to ''guess'' a correct circuit for SAT. The complexity class $\backslash Sigma\_2$ describes problems of the form :$\backslash exists\; x\backslash forall\; y\backslash ;\backslash psi(x,y)$ where $\backslash psi$ is any polynomial-time computable predicate. The existential power of the first quantifier in this predicate can be used to guess a correct circuit for SAT, and the universal power of the second quantifier can be used to verify that the circuit is correct. Once this circuit is guessed and verified, the algorithm in class $\backslash Sigma\_2$ can use it as a subroutine for solving other problems. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Karp–Lipton theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.